README.md

74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true 

Example 2:

Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 Output: false 

Solutions (Rust)

1. Binary Search

implSolution{pubfnsearch_matrix(matrix:Vec<Vec<i32>>,target:i32) -> bool{if matrix.len() == 0{returnfalse;}let m = matrix.len();let n = matrix[0].len();letmut l = 0;letmut r = m * n;while l < r {let mid = (l + r) / 2;let row = mid / n;let col = mid % n;if target == matrix[row][col]{returntrue;}elseif target < matrix[row][col]{ r = mid;}else{ l = mid + 1;}}false}}